package com.booby.algorithm.count;

import com.booby.algorithm.utils.Utils;

/**
 * 功能描述: 计数排序，简单不稳定版本，
 *
 * @author: lizt
 * @date: 2020/8/28 09:13
 **/

public class SimpleVersion {

    public static Integer[] arr = {2, 4, 2, 3, 7, 1, 1, 0, 0, 5, 6, 9, 8, 5, 7, 4, 0, 9};
    public static final int MIN = 0;
    public static final int MAX = 9;

    public static void sorted(Integer[] arr){

        Integer[] count = new Integer[MAX - MIN + 1];
        // 非基本类型初始化数据为null
        for (int i = 0; i < count.length ; i++) {
            count[i] = 0;
        }
        // count数组记录每个数字出现次数
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i] - MIN;
            count[index]++;
        }
        // 临时数组，
        Integer[] temp = new Integer[arr.length];
        int m = 0;
        for (int i = 0; i < count.length ; i++) {
            // count集合中的每个元素出现次数总和即为arr长度
            int e = count[i];
            for (int j = 0; j < e; j++) {
                int value = MIN + i;
                temp[m] = value;
                m++;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = temp[i];
        }
    }
    public static void main(String[] args) {
        sorted(arr);
        Utils.print(arr);
    }
}
